Planning, Fast and Slow

Software Engineering Ph.D. student, Ashutosh Pandey, is coming at autonomous systems a bit differenly: developing a framework for hybrid planning in self-adaptive systems.

In the 2011 best-selling book Thinking, Fast and Slow, Daniel Kahneman suggests that humans think in two distinct modes. The first mode is fast, instinctual and driven by emotion. The second is slower, deliberative, and based in logic.

It was this book that Dr. David Garlan suggested Ashutosh Pandey, then a new Software Engineering PhD student consider. “David asked me if we might be able to tackle the issue of decision making in autonomous systems in a similar way,” Pandey recounts, “The ability to plan is one of the fundamental requirements for autonomous systems, which seek to adapt their behavior in response to a changing environment. To devise a plan, systems utilize planners that determine an adaptation plan based on various factors such as the current state of the system and its operating environment, a set of possible adaptation actions, and the adaptation goal. In simple terms, a plan is a sequence of actions that takes a system from the current state to the goal state.”

While this may seem like a simple enough challenge, this is far from the case. “When the system is making a decision, often it has to strike a balance between the timeliness and quality of planning”, Pandey explains. Until now, the solution has been to handcraft a planner that can reasonably balance timeliness and quality of planning. While sometimes successful, this approach is time-consuming and costly since it requires deep understanding of the operating domain and experience in planning technology.

To overcome the shortcomings of handcrafted planners, Pandey proposed the idea of hybrid planning – a method of planning that combines multiple off-the-shelf reactive and deliberative planners to balance timeliness and quality. The key idea underpinning this approach is to use reactive planning to provide a quick – but potentially a suboptimal – response to a problem, while simultaneously invoking deliberative planning that is likely to provide a higher-quality plan. Once the deliberative plan is ready, it takes over execution from the reactive plan to provide a higher-quality adaptation.

Take, for example, a cloud-based web application servicing clients’ requests. This web app suddenly experiences a spike in request arrival rate. When using hybrid planning, a reactive planner would provide a quick plan to add a server to offset the load. However, in the background, the deliberative planner might develop a more efficient plan by considering possible request arrival rate in the future. Once the plan is ready, it will take over from the reactive plan to provide a higher quality adaptation from there on. Consequently, the system not only responds rapidly to the immediate problem, but also provides a high quality longer-term plan.

“However, to date, much of this hybridization has been through trial-and-error,” Pandey points out. “Developers would mix and match planners until they got the balance right.”

A researcher to his core, Pandey set out to address this problem as all good researchers should: by defining the problem. “There was no formal description of what the hybrid planning problem even is,” he notes. “Developers knew they were trying to optimize a plan but they had no definition of what optimal means.”

And so Pandey, alongside Garlan, set out to write a formal model which would define the problem of hybrid planning. What Pandey discovered was that the hybrid planning problem is, in part, an issue of scale and specialization. Planners exist on a spectrum ranging from extremely deliberative to extremely reactive. Considering all possible planners would result in an infinite number of possible configurations. Part of any possible approach to the hybrid planning problem had to, in some way, provide developers the ability to select a finite number of suitable planners to consider.

As a part of his thesis, Pandey, is addressing this concern by providing a set of guidelines, which will allow system designers/developers to compare the characteristics of their system against a set of benchmarks to determine which types of planners are appropriate to instantiate hybrid planning. “This will narrow the scope of possible planners dramatically,” Pandey explains.

With a general set of possible planners at their disposal, developers would then have to grapple with two significant hurdles to apply hybrid planning. The first challenge is coordinating constituent planners of a hybrid planner. To balance quality and timeliness, hybrid planning requires a smooth transition from a reactive plan to a possibly higher-quality deliberative plan. However, this can be tricky, particularly, under uncertainty when a reactive plan may take a system to a state not anticipated by deliberative planning; thus preventing any transition from a reactive to a deliberative plan.

The second hurdle is to select an appropriate subset planners from the general set of planners to determine a plan in response to a situation; this subset can vary from one adaptation situation to another. Moreover, a proper ordering of plans determined by the planners in the subset is also critical to a successful adaptation. Pandey is developing a machine learning driven approach that will compare an existing system state against planning problems which it has observed in the past. For the existing state, the system will pursue a similar subset and ordering of plans that worked best for past similar problems. “The efficiency of this approach will only increase over time,” Pandey points out. “As the system operates over a period of time it is likely to experience more unique planning problems, its dataset will grow and it will become less and less likely to make a mistake.” In future, he plans to explore how to identify such unique problems at run time and improve the learned model online.

As he nears the finishing line, putting the final touches on his work, Pandey is excited for what the future holds while also profoundly introspective about his time in the program. “The point of the software engineering PhD is to bridge the gap between theory and practice,” he explains. “My work took the spirit of the program - and a significant portion of its approach to problem solving - and applied it to this hybrid planning challenge. At the end of the day, I am just hopeful that what I’ve done as a part of ISR will help take autonomous systems to the next level.”